package leetcode.eazy;


import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。
 * <p>
 * 提示：
 * 1 <= nums.length <= 104
 * -104 <= nums[i] <= 104
 * nums 已按 非递减顺序 排序
 * <p>
 * 进阶：
 * 请你设计时间复杂度为 O(n) 的算法解决本问题
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/squares-of-a-sorted-array
 */
public class SquaresOfASortedArray_977 {
    /**
     * 最小堆实现
     *
     * @param nums
     * @return
     */

    public static int[] sortedSquares1(int[] nums) {
        int len = nums.length;
        int[] ans = new int[len];
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(a -> a));
        for (int i = 0; i < len; i++) {
            priorityQueue.add(nums[i] * nums[i]);
        }
        for (int j = 0; j < len; j++) {
            ans[j] = priorityQueue.poll();
        }
        return ans;
    }

    /**
     * 利用Arrays.sort()
     *
     * @param nums
     * @return
     */
    public static int[] sortedSquares5(int[] nums) {
        int[] ans = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            ans[i] = nums[i] * nums[i];
        }
        Arrays.sort(ans);
        return ans;
    }


    /**
     * 复习一下排序算法
     *
     * @param nums
     * @return
     */
    public static int[] sortedSquares2(int[] nums) {
        int len = nums.length;
        int[] ans = new int[len];
        for (int i = 0; i < len; i++) {
            ans[i] = nums[i] * nums[i];
        }
//        bubbleSort(len, ans);
//        selectionSort(len, ans);
        insertionSort(len, ans);
        return ans;
    }

    /**
     * 双指针
     *
     * @param nums
     * @return
     */
    public static int[] sortedSquares3(int[] nums) {
        int len = nums.length;
        int[] ans = new int[len];
        int l = 0, r = len - 1;
        for (int i = len - 1; i >= 0; i--) {
            if (nums[l] * nums[l] > nums[r] * nums[r] && l < r) {
                ans[i] = nums[l] * nums[l];
                l++;
            } else {
                ans[i] = nums[r] * nums[r];
                r--;
            }
        }
        return ans;
    }

    /**
     * 插入排序
     *
     * @param len
     * @param ans
     */
    private static void insertionSort(int len, int[] ans) {
        for (int i = 1; i < len; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (ans[j] > ans[j + 1]) {
                    int tmp = ans[j];
                    ans[j] = ans[j + 1];
                    ans[j + 1] = tmp;
                }
            }
        }
    }

    /**
     * 选择排序，每次循环找出未排序区间内最小的元素
     *
     * @param len
     * @param ans
     */
    private static void selectionSort(int len, int[] ans) {
        int minIndex = len;
        for (int i = 0; i < len - 1; i++) {
            for (int j = i; j < len - 1; j++) {
                minIndex = ans[j] < ans[j + 1] ? j : j + 1;
            }
            int tmp = ans[i];
            ans[i] = ans[minIndex];
            ans[minIndex] = tmp;
        }
    }

    /**
     * 依次比较相邻两个元素的大小
     *
     * @param len
     * @param ans
     */
    private static void bubbleSort(int len, int[] ans) {
        for (int i = 0; i < len - 1; i++) {
            for (int j = 0; j < len - 1 - i; j++) {
                if (ans[j] > ans[j + 1]) {
                    int tmp = ans[j];
                    ans[j] = ans[j + 1];
                    ans[j + 1] = tmp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] nums = {-3, -3, -2, 1};
        System.out.println(Arrays.toString(sortedSquares3(nums)));
//        System.out.println( (int) (Math.pow(2,31) - 1) );
    }
}
